package datastructure.book.tujiesuanfa.arr.solution._2_more;

import datastructure.book.tujiesuanfa.list.bean.ListNode;
import datastructure.book.tujiesuanfa.list.bean.Node;

import java.util.LinkedList;

public class Solution1 {
    /**
     * 将所有奇数调整至偶数之前，可以不考虑顺序
     * 只遍历一遍数组
     * 示例 1：
     * 输入：actions = [1,2,3,4,5]
     * 输出：[1,3,5,2,4]或者[1,5,3,2,4]
     */
    public int[] trainingPlan(int[] actions) {
        //左右双指针往中间遍历
        if (actions == null || actions.length == 0) {
            return actions;
        }
        int left = 0;int right = actions.length-1;
        int dir = 0;
        while (left < right) {
            if (dir == 0) {
                while (actions[left] % 2 != 0) {
                    if (left < right) {
                        left++;
                    } else {
                        return actions;
                    }
                }
                dir = 1;
            } else {
                while (actions[right] % 2 == 0) {
                    if (left < right) {
                        right--;
                    } else {
                        return actions;
                    }
                }
                int temp = actions[left];
                actions[left] = actions[right];
                actions[right] = temp;
                right--;
                left++;
                dir = 0;
            }
        }
        return actions;
    }

    public int[] trainingPlan2(int[] actions) {
        //左右双指针往中间遍历
        if (actions == null || actions.length == 0) {
            return actions;
        }
        int left = 0;int right = actions.length-1;
        while (left < right) {
            //左侧找偶数，右侧找奇数
            while (actions[left] % 2 != 0) {
                if (left < right) {
                    left++;
                } else {
                    return actions;
                }
            }
            while (actions[right] % 2 == 0) {
                if (left < right) {
                    right--;
                } else {
                    return actions;
                }
            }
            int temp = actions[left];
            actions[left] = actions[right];
            actions[right] = temp;
            left++;right--;
        }
        return actions;
    }

    /**
     * 连续正整数（至少2个）总和为指定数字 target 的所有组合
     * 例1：
     * 输入：target = 12
     * 输出：[[3, 4, 5]]
     * 例2：
     * 输入：target = 18
     * 输出：[[3,4,5,6],[5,6,7]]
     */
    public int[][] fileCombination(int target) {
        //滑动窗口，窗口大小小于2时结束
        LinkedList<int[]> resultList = new LinkedList<>();
        int left = 1;int right = 2;int cnt = 3;
        while (left < right) {
            if (cnt < target) {
                right++;
                cnt+=right;
            } else if (cnt > target) {
                cnt -= left;
                left++;
            } else {
                int[] ints = new int[right - left + 1];
                for (int i = 0,j = left; i < ints.length; i++,j++) {
                    ints[i] = j;
                }
                resultList.add(ints);
                right++;
                cnt+=right;
            }
        }
        return resultList.toArray(new int[0][]);
    }

    /**
     * 返回数组arrayB，arrayB[i] = arrayA除去第i个元素其余元素的乘积
     * arrayA中有可能有0
     * 不能使用除法，时间复杂度为O(N)，空间复杂度为O(1)
     * 例如：
     * 输入：arrayA = [2, 4, 6, 8, 10]
     * 输出：[1920, 960, 640, 480, 384]
     */
    public int[] statisticalResult(int[] arrayA) {
        if (arrayA == null || arrayA.length == 0) {
            return arrayA;
        }
        int[] result = new int[arrayA.length];
        result[0] = 1;
        int product = 1;
        for (int i = 1; i < arrayA.length; i++) {
            product = product*arrayA[i-1];
            result[i] = product;
        }
        product = 1;
        for (int i = arrayA.length - 2; i >=0; i--) {
            product = product*arrayA[i+1];
            result[i] = product*result[i];
        }
        return result;
    }

    /**
     * 螺旋遍历数组：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，
     * 然后再进入内部一层重复相同的步骤，直到提取完所有元素。
     * 示例 1：
     * 输入：array = [
     *          [1,2,3],
     *          [8,9,4],
     *          [7,6,5]]
     * 输出：[1,2,3,4,5,6,7,8,9]
     */
    public int[] spiralArray(int[][] array) {
        if (array == null || array.length == 0) {
            return new int[0];
        }
        int[] result = new int[array.length * array[0].length];
        int low = array.length;int line = array[0].length;
        int tep = 0;int x = 0;int y = 0;
        while (tep < result.length) {
            for (int i = 0; i < line; i++,tep++) {
                result[tep] = array[x][y];
                y++;
            }
            y--;low--;x++;
            if (low < 1) {
                break;
            }
            for (int i = 0; i < low; i++,tep++) {
                result[tep] = array[x][y];
                x++;
            }
            x--;line--;y--;
            if (line < 1) {
                break;
            }
            for (int i = 0; i < line; i++,tep++) {
                result[tep] = array[x][y];
                y--;
            }
            y++;low--;x--;
            if (low < 1) {
                break;
            }
            for (int i = 0; i < low; i++,tep++) {
                result[tep] = array[x][y];
                x--;
            }
            x++;line--;y++;
        }
        return result;
    }

    public int[] spiralArray2(int[][] array) {
        if (array == null || array.length == 0) {
            return new int[0];
        }
        //上下左右边界坐标
        int top = 0,under = array.length-1,left = 0,right = array[0].length-1;
        int[] result = new int[array.length * array[0].length];
        int tep = 0;
        while (tep < result.length) {
            for (int i = left; i <= right; i++) {
                result[tep++] = array[top][i];
            }
            if (++top > under) {
                break;
            }
            for (int i = top; i <= under; i++) {
                result[tep++] = array[i][right];
            }
            if (--right < left) {
                break;
            }
            for (int i = right; i >= left; i--) {
                result[tep++] = array[under][i];
            }
            if (--under < top) {
                break;
            }
            for (int i = under; i >= top; i--) {
                result[tep++] = array[i][left];
            }
            if (++left > right) {
                break;
            }
        }
        return result;
    }
}
